package com.leetcode.partition7;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/11/11 8:07
 */
public class LC629K个逆序对数组 {

    private static final int MOD = 1000000007;

    /**
     * 在推出递推公式的时候，这一步是关键
     * 假如当前的4个数字的排列方式为：xxxx
     * 再往其中添加一个数字5有如下几种添加方式：
     * xxxx5 多出0个逆序对，因此有：f1(5,k)=f(4,k)
     * xxx5x 多出1个逆序对，因此有：f2(5,k+1)=f(4,k)=> f2(5,k)=f(4,k-1)
     * xx5xx 多出1个逆序对，因此有：f3(5,k+2)=f(4,k)=> f3(5,k)=f(4,k-2)
     * x5xxx 多出1个逆序对，因此有：f4(5,k+3)=f(4,k)=> f4(5,k)=f(4,k-3)
     * 5xxxx 多出1个逆序对，因此有：f5(5,k+4)=f(4,k)=> f5(5,k)=f(4,k-4)
     * f(5,k) = f1 + f2 + f3 + ... + f5
     * f(5,k) = f(4,k) + f(4,k-1) + f(4,k-2) + f(4,k-3) + f(4,k-5+1)
     * f(n,k) = f(n-1,k)+f(n-1,k-1) + f(n-1,k-2) + f(n-1,k-3) + ... + f(n-1,k-n+1)
     * f(n,k+1) = f(n-1,k+1) + f(n-1,k-1) + f(n-1,k-2) + ... + f(n-1,k-n+2)
     * 两式相减得：f(n,k+1) - f(n,k) = f(n-1,k+1) - f(n-1,k-n+1)
     * f(n,k+1) = f(n,k) + f(n-1,k+1) - f(n-1,k-n+1)
     * 使用k代替k+1，得：f(n,k) = f(n,k-1) + f(n-1,k) - f(n-1,k-n)
     * 最终递推公式：f(n,k) = f(n,k-1) + f(n-1,k) - f(n-1,k-n)
     */
    public static int kInversePairs(int n, int k) {
        if (k > n * (n - 1) / 2) return 0;
        if (k == 0 || k == n * (n - 1) / 2) return 1;
        //dp[i][j]代表有1-i个数字，且恰好有j对逆序对的方案数。 初始化，所有完全正序列（k=0）、完全逆序列（k=n*(n-1)/2）都为1
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 1; i <= n; i++) dp[i][0] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= Math.min(n * (n - 1) / 2, k); j++) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
                if (j - i >= 0) {
                    dp[i][j] -= dp[i - 1][j - i];
                }
                dp[i][j] = (dp[i][j] + MOD) % MOD;
            }
        }
        Arrays.stream(dp).forEach(val -> System.out.println(Arrays.toString(val)));
        return dp[n][k];
    }

    public static void main(String[] args) {
        System.out.println(kInversePairs(1000, 1000));
    }
}
